Simulated Annealing

Now that we have a fit population, we can try to arrive at an optimal solution starting from each member and traversing the solution space.

Intuition

The algorithm consists of a parameter temperature that regulates the explorative-exploitative tendencies.

Initially, when the temperature is high, the algorithm is highly explorative and tries searching in many different directions, practically randomly, for a better path.

As the temperature progressively decreases, the algorithm progressively becomes more exploitative and goes forward in the most optimal direction found so far, finding an optimum after a number of iterations of this process.

Code snippet

def simulated_annealing(tour, distances, temperature=1000, cooling_rate=0.003, num_iterations=10000):
    current_tour = tour.copy()
    best_tour = tour.copy()
    current_fitness = fitness(current_tour, distances)
    best_fitness = current_fitness

    for i in range(num_iterations):
        new_tour = current_tour[:]
        a, b = random.sample(range(len(new_tour)), 2)
        new_tour[min(a, b): max(a, b) + 1] = new_tour[min(a, b): max(a, b) + 1][::-1]
        new_fitness = fitness(new_tour, distances)
        if new_fitness < current_fitness:
            current_tour = new_tour
            current_fitness = new_fitness
            if new_fitness < best_fitness:
                best_tour = new_tour
                best_fitness = new_fitness
        else:
            acceptance_prob = 1 / (1 + 2.71 ** min((new_fitness - current_fitness) / temperature, 9))
            if random.random() < acceptance_prob:
                current_tour = new_tour
                current_fitness = new_fitness
        temperature *= 1 - cooling_rate

    return best_tour

The fitness of a neighboring tour is computed. If its fitter than the current tour, the algorithm moves to it.

Otherwise, a probability is assigned to it based on how much unfit it is compared to fitness of current tour. The algorithm chooses to travel to it based on this probability.

This means, even for neighboring tours whose fitness is not better than current fitness, there is a non-zero probability of travelling to it. This is explorative.

Initially, when the temperature is high, the probability assigned to travelling to unfit neighbors is higher, encouraging exploration, but as temperature decreases, these probabilities decrease, encouraging the algorithm to only move towards fitter neighbors.

Conclusion

This entire process is repeated starting from each tour of the population, arriving at an optimum. A new population is thus created in which, each of the n members are the optimum points arrived at through Simulated Annealing starting from the corresponding member of the riginal population.